/**
 *  @file MergeCircleSinglink.c
 *  @desc 合并两个循环单链表（带头结点），合并后的链表仍为循环结构，复用原有节点
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-23 16:08
 *  @version 1.0
 */

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

// ------------------------- 结构体定义 -------------------------

/**
 * @brief 循环单链表结点结构体
 */
typedef struct node {
    int data;          ///< 数据域
    struct node *next; ///< 指向下一个节点
} node, *link;

// ------------------------- 链表初始化与节点创建 -------------------------

/**
 * @brief 初始化一个带头结点的循环单链表
 * @param head 链表头指针的地址
 */
void initNode(link *head) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return;
    newNode->data = 0;       // 头结点不存储有效数据
    newNode->next = newNode; // 自己指向自己，形成循环
    *head = newNode;
}

/**
 * @brief 创建一个存储具体值的新结点
 * @param value 要存储的整数值
 * @return 成功返回新结点指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// ------------------------- 插入操作 -------------------------

/**
 * @brief 头插法：将新结点插入到头结点之后
 * @param head 循环链表头指针
 * @param value 插入的值
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = head->next;
    head->next = newNode;
}

/**
 * @brief 尾插法：将新结点插入到链表尾部（即头结点前）
 * @param head 循环链表头指针
 * @param value 插入的值
 */
void istTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    link cur = head;
    // 找到尾节点（即 next 指向 head 的节点）
    while (cur->next != head) {
        cur = cur->next;
    }
    cur->next = newNode;
    newNode->next = head;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 打印循环链表中所有数据（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;
    while (cur != head) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 合并两个循环单链表 -------------------------

/**
 * @brief 合并两个循环单链表，合并后的链表仍为循环结构
 * @param la 第一个循环链表（带头结点）
 * @param lb 第二个循环链表（带头结点）
 * @return 返回合并后的链表头指针（仍为 la 的头结点）
 */
link mergeLink(link la, link lb) {
    // 如果 la 是空表或只有头结点，返回 lb
    if ((la == NULL || la->next == la)) return lb;

    // 如果 lb 是空表或只有头结点，返回 la
    if ((lb == NULL || lb->next == lb)) return la;

    // 找到 la 的尾节点（next 指向 la 的节点）
    link pa = la;
    while (pa->next != la) {
        pa = pa->next;
    }

    // 找到 lb 的尾节点（next 指向 lb 的节点）
    link pb = lb;
    while (pb->next != lb) {
        pb = pb->next;
    }

    // 拼接链表：la 尾 -> lb 的首数据结点（跳过 lb 的头结点）
    pa->next = lb->next;

    // lb 尾 -> la 的头结点，保持循环
    pb->next = la;

    return la; // 返回合并后的循环链表
}

// ------------------------- 主函数测试 -------------------------

int main() {
    // 初始化第一个链表 head，并插入 1 2 3
    link head = NULL;
    initNode(&head);
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);
    printf("List A:\n");
    printList(head);

    // 初始化第二个链表 head1，并插入 1 2 3
    link head1 = NULL;
    initNode(&head1);
    istTail(head1, 1);
    istTail(head1, 2);
    istTail(head1, 3);
    printf("List B:\n");
    printList(head1);

    // 合并两个循环链表
    mergeLink(head, head1);
    printf("Merged List:\n");
    printList(head);  // 合并结果打印
}
